package algorithm.t202110;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/21 8:41
 * @description :3道
 * 蓦然回首，那人却在，灯火阑珊处。
 * persevere to last
 * -2021.10.21
 */
public class t20211021 {


    //77.组合
    public List<List<Integer>> combine(int n, int k) {

        ArrayList<List<Integer>> res = new ArrayList<>();


        if (n == 0 || k == 0) {
            return res;
        }

        ArrayDeque<Integer> deque = new ArrayDeque<>();

        deep(n, k, 1, deque, res);
        return res;
    }

    //n数字大小限制，k数字长度限制，begin其实数字，deque存放数字组合，res待返回的结果
    private void deep(int n, int k, int begin, ArrayDeque<Integer> deque, ArrayList<List<Integer>> res) {

        //临界条件，当队列的大小等于长度限制，将这个组合加入到res
        if (deque.size() == k) {
            res.add(new ArrayList<>(deque));
            return;
        }

        for (int i = begin; i <= n; i++) {
            deque.offer(i);
            //这里我们递归调用begin+1是为了防止重复元素
            deep(n, k, i + 1, deque, res);//组合不是排列，如1,2  2,1是一个组合，而1,2 2,1是两个排列

            deque.removeLast();

        }

    }

    //46.全排列  深度优先遍历
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null) {
            return null;
        }

        ArrayList<List<Integer>> res = new ArrayList<>();
        if (nums.length == 1) {

            ArrayList<Integer> list = new ArrayList<>();
            list.add(nums[0]);
            res.add(list);
            return res;
        }


        int len = nums.length;

        boolean[] used = new boolean[nums.length];//用于防止重复访问

        Deque<Integer> deque = new ArrayDeque<>();


        deep2(0, nums, len, deque, used, res);
        return res;

    }

    private void deep2(int depth, int[] nums, int len, Deque<Integer> deque, boolean[] used, ArrayList<List<Integer>> res) {

        if (depth == len) {
            res.add(new ArrayList<>(deque));
            return;
        }

        for (int i = 0; i < len; i++) {
            if (used[i]) {
                continue;
            }
            deque.offer(nums[i]);
            used[i] = true;

            deep2(depth + 1, nums, len, deque, used, res);

            deque.removeLast();
            used[i] = false;

        }

    }

    //784.字母大小全排列
    public List<String> letterCasePermutation(String s) {
        ArrayList<String> res = new ArrayList<>();
        if (res == null) {
            return res;
        }

        char[] chars = s.toCharArray();

        deep3(0, chars, res);

        return res;


    }

    private void deep3(int index, char[] chars, ArrayList<String> res) {
        if (index == chars.length) {
            res.add(new String(chars));
            return;
        }

        deep3(index + 1, chars, res);

        if (Character.isLetter(chars[index])) {
            chars[index] = (char) (chars[index] ^ 1 << 5);
            deep3(index + 1, chars, res);
        }

    }


    public static void main(String[] args) {
        t20211021 t20211021 = new t20211021();

        t20211021.combine(4, 2);

        List<List<Integer>> list = t20211021.permute(new int[]{1, 2, 3});

        String str = "a1b";
        List<String> stringList = t20211021.letterCasePermutation(str);
        for (String s : stringList) {
            System.out.println(s);
        }


    }


}
